package leetcode.graph.dfs.p695;

import java.util.HashSet;

/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.p695 
 * @Description: 695. 岛屿的最大面积
 *                  根据给定的二维数组构建邻接表
 * @author CandyWall   
 * @date 2021年1月16日 上午11:31:07 
 * @version V1.0
 */
class Solution_v1 {
    private int R,C;
    private int[][] grid;
    private HashSet<Integer>[] graph;
    private boolean[] visited;
    
    private int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    
    public int maxAreaOfIsland(int[][] grid) {
        if(grid == null) {
            return 0;
        }
        if(grid.length == 0) {
            return 0;
        }
        R = grid.length;
        if(grid[0].length == 0) {
            return 0;
        }
        C = grid[0].length;
        this.grid = grid;
        
        constructGraph(grid);
        
        int res = 0;
        visited = new boolean[graph.length];
        for(int v = 0; v < graph.length; v++) {
            int x = v / C, y = v % C;
            if(!visited[v] && grid[x][y] == 1) {
                int count = dfs(v);
                if(res < count) {
                    res = count;
                }
            }
        }
        
        return res;
    }
    
    // 深度优先遍历
    private int dfs(int v) {
        visited[v] = true;
        int count = 1;
        for(int w : graph[v]) {
            if(!visited[w]) {
                count += dfs(w);
            }
        }
        return count;
    }

    // 根据给定的二维数组建图
    private void constructGraph(int[][] grid) {
        // 邻接表初始化
        graph = new HashSet[R * C];
        for(int i = 0; i < graph.length; i++) {
            graph[i] = new HashSet<>();
        }
        
        for(int v = 0; v < graph.length; v++) {
            int x = v / C, y = v % C;
            // 根据土地进行建图
            if(grid[x][y] == 1) {
                for(int d = 0; d < 4; d++) {
                    int nextX = x + dirs[d][0];
                    int nextY = y + dirs[d][1];
                    if(inArea(nextX, nextY) && grid[nextX][nextY] == 1) {
                        int next = nextX * C + nextY;
                        graph[v].add(next);
                        graph[next].add(v);
                    }
                }
            }
        }
    }

    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
    
    public static void main(String[] args) {
        int[][] grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,0,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,0,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};
        System.out.println(new Solution_v1().maxAreaOfIsland(grid));
    }
}
